package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-24 16:44
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 */
public class lc77 {
    public List<List<Integer>> combine(int n, int k) {

        //题目给定从1开始
        dfs(1,n,k);
        return ans;
    }

    List<Integer> temp = new ArrayList<>();//临时存放数据的数组
    List<List<Integer>> ans = new ArrayList<>();//所有结果数组；

    public void dfs(int cur, int n, int k) {

        //减枝，temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }

        //长度达到k ,记录合法的答案
        if (temp.size() == k) {
            ans.add(new ArrayList<Integer>(temp));
            return;
        }

        // 考虑选择当前位置
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);//恢复现场，即回溯

        // 考虑不选择当前位置
        dfs(cur + 1, n, k);

    }
}
